Codeforces Round 265(Div. 2)

Diposting di | Edited on

传送门

[A - inc ARG(签到)

题意

给你一个二进制数，问你加1之后有多少位会变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    string s;
    cin>>n>>s;
    int num=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1')num++;
        else break;
    }
    cout<<min(num+1,n)<<endl;
}

B - Inbox (100500) （水）

题意

一个电子邮箱，两种状态一种目录状态可以去在这里去任意一个信件，一种是浏览模式可以进到信件里面，如果这个信件是未读的就会变成已读，在浏览模式里面可以选择进入下一份相邻信件的浏览模式。每次点击可以进入目录模式or浏览模式or进入下一个相邻信件

问你最少多少次可以吧所有信件变成已读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
const int maxn=1300;
int a[maxn];
int main(){

    int n,num=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int first=0;
    for(int i=1;i<=n;i++){
        if((a[i]==1&&a[i-1]==1)||(!first&&a[i]==1))num++,first=1;
        else if(a[i]==1&&a[i-1]==0)num+=2;
    }
    cout<<num<<endl;
    return 0;
}

C - No to Palindromes! (暴力模拟)

题意

给你一个不是回文的字符串，只能用不超过‘K的字符。问你这个字符串还大的字典序并且不是回文的字符串是什么

思路

首先如果改变的那一位的相邻两位不一样和隔一位不一样就不可能有回文

直接从后面暴力枚举状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int maxn=1300;

char s[maxn];
int n,p;
bool check(int pos){
    if(pos>=1){
        if(s[pos]==s[pos-1])return false;
    }
    if(pos>=2){
        if(s[pos]==s[pos-2])return false;
    }
    return true;
}
int main(){
    cin>>n>>p;
    cin>>s;
    int pos=n-1;
    while(true){
       // cout<<"pos="<<pos<<endl;
       // cout<<"s="<<s<<endl;
        if(pos==n)cout<<s<<endl,exit(0);
        if(pos==-1)cout<<"NO"<<endl,exit(0);
        if(s[pos]-'a'+1==p){
            s[pos]='a'-1;pos--;
            continue;
        }
        else{
            s[pos]=(s[pos]-'a'+1)%p+'a';
            if(check(pos)){
                pos++;
            }
        }

    }
    return 0;
}

D - Restore Cube (模拟，深搜)

题意

给你一个八面体，八面体的每个顶点的坐标x,y,z被打乱了，问你是否原来的是一个正方体

思路

直接暴力枚举复杂度是6^8 然后判断是否符合正方体的性质即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1300;
vector<ll>v[8];
ll get(int x){
    return 1LL*x*x;
}
ll dist(vector<ll> a,vector<ll> b){
    return get(a[0]-b[0])+get(a[1]-b[1])+get(a[2]-b[2]);
}
void prin(vector<ll> a){
    for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
    cout<<endl;
}
bool diff(){
    for(int i=0;i<8;i++){
        for(int j=i+1;j<8;j++){
            if(v[i]==v[j])return true;
        }
    }
    return false;
}
void dfs(int id,set<ll> a){
    if(a.size()>3)return ;
    if(id==8){
        if(a.size()==3){
            cout<<"YES"<<endl;
            for(int i=0;i<8;i++)prin(v[i]);
            exit(0);
        }
        return;
    }
    do{
        set<ll>now=a;
        for(int i=0;i<id;i++)now.insert(dist(v[i],v[id]));
        dfs(id+1,now);
    }while(next_permutation(v[id].begin(),v[id].end()));
}

int main(){
    for(int i=0;i<8;i++){
        for(int j=0;j<3;j++){
            ll a;cin>>a;
            v[i].push_back(a);
        }
        sort(v[i].begin(),v[i].end());
    }
    set<ll>s;
    dfs(0,s);
    cout<<"NO"<<endl;
    return 0;
}

E - Substitutes in Number (模拟 费马小定理)

题意

给出一个数字字符串，每次操作把一个数字替换成一个数字字符串，

之后把整个数字字符串变成十进制输出

思路

暴力肯定爆炸字符串长度是指数上升的。

一开始 要获得字符串中一个数字的价值是 原值*10+val 所以原本一个数字的贡献是 其中的$\times$ 和val 发现替换也就是在替换这个val和$\times$

我们从后模拟被替换的字符串的价值和$\times$ 就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
const ll mod=1e9+7;
#define bug cout<<"hello"<<endl;
int n;
ll ksm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
ll val[20],len[20];
struct node{
    string s;
    int id;
    vector<int>v;
    void build(){
        id=s[0]-'0';
        for(int i=3;i<s.size();i++){
            v.push_back(s[i]-'0');
        }
    }
    void update(){
        ll l=0,va=0;
        for(int i=0;i<v.size();i++){
            l+=len[v[i]];
            va*=ksm(10LL,len[v[i]]);
            va%=mod;
            va+=val[v[i]];
            va%=mod;
            l%=mod-1;
        }
        val[id]=va;len[id]=l;
    }
}my[maxn];
string str;
int main(){
    for(int i=0;i<10;i++)val[i]=i,len[i]=1;
    cin>>str;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>my[i].s;
        my[i].build();
    }

    for(int i=n;i;i--){
        my[i].update();
    }
    ll ans=0;
    for(int i=0;i<str.size();i++){
        ans*=ksm(10,len[str[i]-'0']);
        ans%=mod;
        ans+=val[str[i]-'0'];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}